home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / access / nobtree / nobtpage.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  13.1 KB  |  528 lines
  1. /*
  2.  *  btpage.c -- BTree-specific page management code for the Postgres btree
  3.  *            access method.
  4.  *
  5.  *  Postgres btree pages look like ordinary relation pages.  The opaque
  6.  *  data at high addresses includes pointers to left and right siblings
  7.  *  and flag data describing page state.  The first page in a btree, page
  8.  *  zero, is special -- it stores meta-information describing the tree.
  9.  *  Pages one and higher store the actual tree data.
  10.  */
  11.  
  12. #include "tmp/c.h"
  13. #ifdef NOBTREE
  14. #include "tmp/postgres.h"
  15.  
  16. #include "storage/bufmgr.h"
  17. #include "storage/bufpage.h"
  18. #include "storage/page.h"
  19.  
  20. #include "utils/log.h"
  21. #include "utils/rel.h"
  22. #include "utils/excid.h"
  23.  
  24. #include "access/genam.h"
  25. #include "access/ftup.h"
  26. #include "access/nobtree.h"
  27.  
  28. RcsId("$Header: /private/postgres/src/access/nobtree/RCS/nobtpage.c,v 1.7 1991/10/29 20:21:44 mer Exp $");
  29.  
  30. #define BTREE_METAPAGE    0
  31. #define BTREE_MAGIC    0x053162
  32. #define BTREE_VERSION    0
  33.  
  34. typedef struct BTMetaPageData {
  35.     uint32    btm_magic;
  36.     uint32    btm_version;
  37.     BlockNumber    btm_root;
  38.     BlockNumber    btm_freelist;
  39. } BTMetaPageData;
  40.  
  41. /*
  42.  *  _nobt_metapinit() -- Initialize the metadata page of a btree.
  43.  */
  44.  
  45. _nobt_metapinit(rel)
  46.     Relation rel;
  47. {
  48.     Buffer buf;
  49.     Page pg;
  50.     int nblocks;
  51.     BTMetaPageData metad;
  52.  
  53.     /* can't be sharing this with anyone, now... */
  54.     RelationSetLockForWrite(rel);
  55.  
  56.     if ((nblocks = RelationGetNumberOfBlocks(rel)) != 0) {
  57.     elog(WARN, "Cannot initialize non-empty btree %s",
  58.            rel->rd_rel->relname);
  59.     }
  60.  
  61.     buf = ReadBuffer(rel, P_NEW);
  62.     pg = BufferGetPage(buf, 0);
  63.  
  64.     metad.btm_magic = BTREE_MAGIC;
  65.     metad.btm_version = BTREE_VERSION;
  66.     metad.btm_root = P_NONE;
  67.     metad.btm_freelist = P_NONE;
  68.  
  69.     bcopy((char *) &metad, (char *) pg, sizeof(metad));
  70.  
  71.     WriteBuffer(buf);
  72.  
  73.     /* all done */
  74.     RelationUnsetLockForWrite(rel);
  75. }
  76.  
  77. /*
  78.  *  _nobt_checkmeta() -- Verify that the metadata stored in a btree are
  79.  *               reasonable.
  80.  */
  81.  
  82. _nobt_checkmeta(rel)
  83.     Relation rel;
  84. {
  85.     Buffer metabuf;
  86.     BTMetaPageData *metad;
  87.     int nblocks;
  88.  
  89.     /* if the relation is empty, this is init time; don't complain */
  90.     if ((nblocks = RelationGetNumberOfBlocks(rel)) == 0)
  91.     return;
  92.  
  93.     metabuf = _nobt_getbuf(rel, BTREE_METAPAGE, NOBT_READ);
  94.     metad = (BTMetaPageData *) BufferGetPage(metabuf, 0);
  95.  
  96.     if (metad->btm_magic != BTREE_MAGIC) {
  97.     elog(WARN, "What are you trying to pull?  %s is not a btree",
  98.            rel->rd_rel->relname);
  99.     }
  100.  
  101.     if (metad->btm_version != BTREE_VERSION) {
  102.     elog(WARN, "Version mismatch on %s:  version %d file, version %d code",
  103.            rel->rd_rel->relname, metad->btm_version, BTREE_VERSION);
  104.     }
  105.  
  106.     _nobt_relbuf(rel, metabuf, NOBT_READ);
  107. }
  108.  
  109. /*
  110.  *  _nobt_getroot() -- Get the root page of the btree.
  111.  *
  112.  *    Since the root page can move around the btree file, we have to read
  113.  *    its location from the metadata page, and then read the root page
  114.  *    itself.  If no root page exists yet, we have to create one.  The
  115.  *    standard class of race conditions exists here; I think I covered
  116.  *    them all in the Hopi Indian rain dance of lock requests below.
  117.  *
  118.  *    We pass in the access type (NOBT_READ or NOBT_WRITE), and return the
  119.  *    root page's buffer with the appropriate lock type set.  Reference
  120.  *    count on the root page gets bumped by ReadBuffer.  The metadata
  121.  *    page is unlocked and unreferenced by this process when this routine
  122.  *    returns.
  123.  */
  124.  
  125. Buffer
  126. _nobt_getroot(rel, access)
  127.     Relation rel;
  128.     int access;
  129. {
  130.     Buffer metabuf;
  131.     Buffer rootbuf;
  132.     Page rootpg;
  133.     NOBTPageOpaque rootopaque;
  134.     BlockNumber rootblkno;
  135.     BTMetaPageData *metad;
  136.  
  137.     metabuf = _nobt_getbuf(rel, BTREE_METAPAGE, NOBT_READ);
  138.     metad = (BTMetaPageData *) BufferGetPage(metabuf, 0);
  139.  
  140.     /* if no root page initialized yet, do it */
  141.     if (metad->btm_root == P_NONE) {
  142.  
  143.     /* turn our read lock in for a write lock */
  144.     _nobt_relbuf(rel, metabuf, NOBT_READ);
  145.     metabuf = _nobt_getbuf(rel, BTREE_METAPAGE, NOBT_WRITE);
  146.     metad = (BTMetaPageData *) BufferGetPage(metabuf, 0);
  147.  
  148.     /*
  149.      *  Race condition:  if someone else initialized the metadata between
  150.      *  the time we released the read lock and acquired the write lock,
  151.      *  above, we want to avoid doing it again.
  152.      */
  153.  
  154.     if (metad->btm_root == P_NONE) {
  155.  
  156.         /*
  157.          *  Get, initialize, write, and leave a lock of the appropriate
  158.          *  type on the new root page.  Since this is the first page in
  159.          *  the tree, it's a leaf.
  160.          */
  161.  
  162.         rootbuf = _nobt_getbuf(rel, P_NEW, NOBT_WRITE);
  163.         rootblkno = BufferGetBlockNumber(rootbuf);
  164.         rootpg = BufferGetPage(rootbuf, 0);
  165.         metad->btm_root = rootblkno;
  166.         _nobt_pageinit(rootpg);
  167.         rootopaque = (NOBTPageOpaque) PageGetSpecialPointer(rootpg);
  168.         rootopaque->nobtpo_flags |= (NOBTP_LEAF | NOBTP_ROOT);
  169.         _nobt_wrtnorelbuf(rel, rootbuf);
  170.  
  171.         /* swap write lock for read lock, if appropriate */
  172.         if (access != NOBT_WRITE) {
  173.         _nobt_setpagelock(rel, rootblkno, NOBT_READ);
  174.         _nobt_unsetpagelock(rel, rootblkno, NOBT_WRITE);
  175.         }
  176.  
  177.         /* okay, metadata is correct */
  178.         _nobt_wrtbuf(rel, metabuf);
  179.     } else {
  180.  
  181.         /*
  182.          *  Metadata initialized by someone else.  In order to guarantee
  183.          *  no deadlocks, we have to release the metadata page and start
  184.          *  all over again.
  185.          */
  186.  
  187.         _nobt_relbuf(rel, metabuf, NOBT_WRITE);
  188.         return (_nobt_getroot(rel));
  189.     }
  190.     } else {
  191.     rootbuf = _nobt_getbuf(rel, metad->btm_root, access);
  192.  
  193.     /* done with the meta page */
  194.     _nobt_relbuf(rel, metabuf, NOBT_READ);
  195.     }
  196.  
  197.     /*
  198.      *  Race condition:  If the root page split between the time we looked
  199.      *  at the metadata page and got the root buffer, then we got the wrong
  200.      *  buffer.
  201.      */
  202.  
  203.     rootpg = BufferGetPage(rootbuf, 0);
  204.     rootopaque = (NOBTPageOpaque) PageGetSpecialPointer(rootpg);
  205.  
  206. #ifdef    SHADOW
  207.     if (!(rootopaque->nobtpo_flags & NOBTP_ROOT)
  208.     || (rootopaque->nobtpo_replaced != P_NONE)) {
  209. #endif    /* SHADOW */
  210. #ifdef    NORMAL
  211.     if (!(rootopaque->nobtpo_flags & NOBTP_ROOT)) {
  212. #endif    /* NORMAL */
  213. #ifdef    REORG
  214.     if (!(rootopaque->nobtpo_flags & NOBTP_ROOT)) {
  215. #endif    /* REORG */
  216.  
  217.     /* it happened, try again */
  218.     _nobt_relbuf(rel, rootbuf, access);
  219.     return (_nobt_getroot(rel));
  220.     }
  221.  
  222.     /*
  223.      *  By here, we have a correct lock on the root block, its reference
  224.      *  count is correct, and we have no lock set on the metadata page.
  225.      *  Return the root block.
  226.      */
  227.  
  228.     return (rootbuf);
  229. }
  230.  
  231. /*
  232.  *  _nobt_getbuf() -- Get a buffer by block number for read or write.
  233.  *
  234.  *    When this routine returns, the appropriate lock is set on the
  235.  *    requested buffer its reference count is correct.
  236.  */
  237.  
  238. Buffer
  239. _nobt_getbuf(rel, blkno, access)
  240.     Relation rel;
  241.     BlockNumber blkno;
  242.     int access;
  243. {
  244.     Buffer buf;
  245.     Page page;
  246.  
  247.     /*
  248.      *  If we want a new block, we can't set a lock of the appropriate type
  249.      *  until we've instantiated the buffer.
  250.      */
  251.  
  252.     if (blkno != P_NEW) {
  253.     _nobt_setpagelock(rel, blkno, access);
  254.     buf = ReadBuffer(rel, blkno);
  255.     } else {
  256.     buf = ReadBuffer(rel, blkno);
  257.     blkno = BufferGetBlockNumber(buf);
  258.     page = BufferGetPage(buf, 0);
  259.     _nobt_pageinit(page);
  260.     _nobt_setpagelock(rel, blkno, access);
  261.     }
  262.  
  263.     /* ref count and lock type are correct */
  264.     return (buf);
  265. }
  266.  
  267. /*
  268.  *  _nobt_relbuf() -- release a locked buffer.
  269.  */
  270.  
  271. void
  272. _nobt_relbuf(rel, buf, access)
  273.     Relation rel;
  274.     Buffer buf;
  275.     int access;
  276. {
  277.     BlockNumber blkno;
  278.  
  279.     blkno = BufferGetBlockNumber(buf);
  280.  
  281.     /* access had better be one of read or write */
  282.     if (access == NOBT_WRITE)
  283.     _nobt_unsetpagelock(rel, blkno, NOBT_WRITE);
  284.     else
  285.     _nobt_unsetpagelock(rel, blkno, NOBT_READ);
  286.  
  287.     ReleaseBuffer(buf);
  288. }
  289.  
  290. /*
  291.  *  _nobt_wrtbuf() -- write a btree page to disk.
  292.  *
  293.  *    This routine releases the lock held on the buffer and our reference
  294.  *    to it.  It is an error to call _nobt_wrtbuf() without a write lock
  295.  *    or a reference to the buffer.
  296.  */
  297.  
  298. void
  299. _nobt_wrtbuf(rel, buf)
  300.     Relation rel;
  301.     Buffer buf;
  302. {
  303.     BlockNumber blkno;
  304.  
  305.     blkno = BufferGetBlockNumber(buf);
  306.     WriteBuffer(buf);
  307.     _nobt_unsetpagelock(rel, blkno, NOBT_WRITE);
  308. }
  309.  
  310. /*
  311.  *  _nobt_wrtnorelbuf() -- write a btree page to disk, but do not release
  312.  *             our reference or lock.
  313.  *
  314.  *    It is an error to call _nobt_wrtnorelbuf() without a write lock
  315.  *    or a reference to the buffer.
  316.  */
  317.  
  318. void
  319. _nobt_wrtnorelbuf(rel, buf)
  320.     Relation rel;
  321.     Buffer buf;
  322. {
  323.     BlockNumber blkno;
  324.  
  325.     blkno = BufferGetBlockNumber(buf);
  326.     WriteNoReleaseBuffer(buf);
  327. }
  328.  
  329. /*
  330.  *  _nobt_pageinit() -- Initialize a new page.
  331.  */
  332.  
  333. _nobt_pageinit(page)
  334.     Page page;
  335. {
  336.     /*
  337.      *  Cargo-cult programming -- don't really need this to be zero, but
  338.      *  creating new pages is an infrequent occurrence and it makes me feel
  339.      *  good when I know they're empty.
  340.      */
  341.  
  342.     bzero(page, BLCKSZ);
  343.  
  344.     PageInit(page, BLCKSZ, sizeof(NOBTPageOpaqueData));
  345. }
  346.  
  347. /*
  348.  *  _nobt_metaproot() -- Change the root page of the btree.
  349.  *
  350.  *    Lehman and Yao require that the root page move around in order to
  351.  *    guarantee deadlock-free short-term, fine-granularity locking.  When
  352.  *    we split the root page, we record the new parent in the metadata page
  353.  *    for the relation.  This routine does the work.
  354.  *
  355.  *    No direct preconditions, but if you don't have the a write lock on
  356.  *    at least the old root page when you call this, you're making a big
  357.  *    mistake.  On exit, metapage data is correct and we no longer have
  358.  *    a reference to or lock on the metapage.
  359.  */
  360.  
  361. _nobt_metaproot(rel, rootbknum)
  362.     Relation rel;
  363.     BlockNumber rootbknum;
  364. {
  365.     Buffer metabuf;
  366.     BTMetaPageData *metap;
  367.  
  368.     uint32    btm_magic;
  369.     uint32    btm_version;
  370.     BlockNumber    btm_root;
  371.     BlockNumber    btm_freelist;
  372.  
  373.     metabuf = _nobt_getbuf(rel, BTREE_METAPAGE, NOBT_WRITE);
  374.     metap = (BTMetaPageData *) BufferGetPage(metabuf, 0);
  375.     metap->btm_root = rootbknum;
  376.     _nobt_wrtbuf(rel, metabuf);
  377. }
  378.  
  379. /*
  380.  *  _nobt_getstackbuf() -- Walk back up the tree one step, and find the item
  381.  *             we last looked at in the parent.
  382.  *
  383.  *    This is possible because we save a bit image of the last item
  384.  *    we looked at in the parent, and the update algorithm guarantees
  385.  *    that if items above us in the tree move, they only move right.
  386.  */
  387.  
  388. Buffer
  389. _nobt_getstackbuf(rel, stack, access)
  390.     Relation rel;
  391.     NOBTStack stack;
  392.     int access;
  393. {
  394.     Buffer buf;
  395.     BlockNumber blkno;
  396.     OffsetIndex start, offind, maxoff;
  397.     OffsetIndex i;
  398.     Page page;
  399.     ItemId itemid;
  400.     int nbytes;
  401.     NOBTIItem iitem;
  402.     NOBTPageOpaque opaque;
  403.  
  404.     blkno = stack->nobts_blkno;
  405.     buf = _nobt_getbuf(rel, blkno, access);
  406.     page = BufferGetPage(buf, 0);
  407.     opaque = (NOBTPageOpaque) PageGetSpecialPointer(page);
  408.     maxoff = PageGetMaxOffsetIndex(page);
  409.  
  410.     nbytes = sizeof(NOBTIItemData);
  411.  
  412.     if (maxoff >= stack->nobts_offset) {
  413.     itemid = PageGetItemId(page, stack->nobts_offset);
  414.     iitem = (NOBTIItem) PageGetItem(page, itemid);
  415.  
  416.     /* if the item is where we left it, we're done */
  417.     if (bcmp((char *) iitem, (char *) (stack->nobts_btitem), nbytes) == 0)
  418.         return (buf);
  419.  
  420.     /* if the item has just moved right on this page, we're done */
  421.     for (i = stack->nobts_offset + 1; i <= maxoff; i++) {
  422.         itemid = PageGetItemId(page, stack->nobts_offset);
  423.         iitem = (NOBTIItem) PageGetItem(page, itemid);
  424.  
  425.         /* if the item is where we left it, we're done */
  426.         if (bcmp((char *) iitem, (char *) (stack->nobts_btitem), nbytes) == 0)
  427.         return (buf);
  428.     }
  429.     }
  430.  
  431.     /* by here, the item we're looking for moved right at least one page */
  432.     for (;;) {
  433.     if ((blkno = opaque->nobtpo_next) == P_NONE)
  434.         elog(FATAL, "my bits moved right off the end of the world!");
  435.  
  436.     _nobt_relbuf(rel, buf, access);
  437.     buf = _nobt_getbuf(rel, blkno, access);
  438.     page = BufferGetPage(buf, 0);
  439.     maxoff = PageGetMaxOffsetIndex(page);
  440.     opaque = (NOBTPageOpaque) PageGetSpecialPointer(page);
  441.  
  442.     /* if we have a right sibling, step over the high key */
  443.     if (opaque->nobtpo_next != P_NONE)
  444.         start = 1;
  445.     else
  446.         start = 0;
  447.  
  448.     /* see if it's on this page */
  449.     for (offind = start; offind <= maxoff; offind++) {
  450.         itemid = PageGetItemId(page, offind);
  451.         iitem = (NOBTIItem) PageGetItem(itemid);
  452.         if (bcmp((char *) iitem, (char *) (stack->nobts_btitem), nbytes) == 0)
  453.         return (buf);
  454.     }
  455.     }
  456. }
  457.  
  458. _nobt_setpagelock(rel, blkno, access)
  459.     Relation rel;
  460.     BlockNumber blkno;
  461.     int access;
  462. {
  463.     ItemPointerData iptr;
  464.  
  465.     ItemPointerSet(&iptr, 0, blkno, 0, 1);
  466.  
  467.     switch (access) {
  468.  
  469.       case NOBT_WRITE:
  470.     RelationSetSingleWLockPage(rel, 0, &iptr);
  471.     break;
  472.  
  473.       case NOBT_READ:
  474.     RelationSetSingleRLockPage(rel, 0, &iptr);
  475.     break;
  476.  
  477.       default:
  478.     break;
  479.     }
  480. }
  481.  
  482. _nobt_unsetpagelock(rel, blkno, access)
  483.     Relation rel;
  484.     BlockNumber blkno;
  485.     int access;
  486. {
  487.     ItemPointerData iptr;
  488.  
  489.     ItemPointerSet(&iptr, 0, blkno, 0, 1);
  490.  
  491.     switch (access) {
  492.  
  493.       case NOBT_WRITE:
  494.     RelationUnsetSingleWLockPage(rel, 0, &iptr);
  495.     break;
  496.  
  497.       case NOBT_READ:
  498.     RelationUnsetSingleRLockPage(rel, 0, &iptr);
  499.     break;
  500.  
  501.       default:
  502.     break;
  503.     }
  504. }
  505.  
  506. void
  507. _nobt_pagedel(rel, tid)
  508.     Relation rel;
  509.     ItemPointer tid;
  510. {
  511.     Buffer buf;
  512.     Page page;
  513.     BlockNumber blkno;
  514.     OffsetIndex offno;
  515.  
  516.     blkno = ItemPointerGetBlockNumber(tid);
  517.     offno = ItemPointerGetOffsetNumber(tid, 0);
  518.  
  519.     buf = _nobt_getbuf(rel, blkno, NOBT_WRITE);
  520.     page = BufferGetPage(buf, 0);
  521.  
  522.     PageIndexTupleDelete(page, offno);
  523.  
  524.     /* write the buffer and release the lock */
  525.     _nobt_wrtbuf(rel, buf);
  526. }
  527. #endif /* NOBTREE */
  528.